Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

The aim of this textbook is to provide undergraduate students with an introduction to the basic theoretical models of computability, and to develop some of the model's rich and varied structure. Students who have already some experience with elementary discrete mathematics will find this a well-paced first course, and a number of supplementary chapters introduce more advanced concepts. The first part of the book is devoted to finite automata and their properties. Pushdown automata provide a broader class of models and enable the analysis of context-free languages. In the remaining chapters, Turing machines are introduced and the book culminates in discussions of effective computability, decidability, and Gödel's incompleteness theorems. Plenty of exercises are provided, ranging from the easy to the challenging. As a result, this text will make an ideal first course for students of computer science.

Machine theory --- Computable functions --- 681.3*F41 --- 681.3*F42 --- 681.3*F43 --- Computability theory --- Functions, Computable --- Partial recursive functions --- Recursive functions, Partial --- Abstract automata --- Abstract machines --- Automata --- Mathematical machine theory --- 681.3*F43 Formal languages: algebraic language theory; classes defined by grammars or automata or by resource-bounded automata; operations on languages (Mathematical logic and formal languages)--See also {681.3*D31} --- Formal languages: algebraic language theory; classes defined by grammars or automata or by resource-bounded automata; operations on languages (Mathematical logic and formal languages)--See also {681.3*D31} --- 681.3*F42 Grammars and other rewriting systems: decision problems; grammar types; parallel rewriting systems; parsing; thue systems (Mathematical logic and formal languages)--See also {681.3*D31} --- Grammars and other rewriting systems: decision problems; grammar types; parallel rewriting systems; parsing; thue systems (Mathematical logic and formal languages)--See also {681.3*D31} --- 681.3*F41 Mathematical logic: computability theory; computational logic; lambda calculus; logic programming; mechanical theorem proving; model theory; proof theory;recursive function theory--See also {681.3*F11}; {681.3*I22}; {681.3*I23} --- Mathematical logic: computability theory; computational logic; lambda calculus; logic programming; mechanical theorem proving; model theory; proof theory;recursive function theory--See also {681.3*F11}; {681.3*I22}; {681.3*I23} --- Machine theory. --- Computable functions. --- Computer science --- Automates mathématiques, Théorie des --- Fonctions calculables --- Constructive mathematics --- Decidability (Mathematical logic) --- Algorithms --- Logic, Symbolic and mathematical --- Recursive functions --- Robotics --- Computers. --- Algorithms. --- Computation by Abstract Devices. --- Algorithm Analysis and Problem Complexity. --- Algorism --- Algebra --- Arithmetic --- Automatic computers --- Automatic data processors --- Computer hardware --- Computing machines (Computers) --- Electronic brains --- Electronic calculating-machines --- Electronic computers --- Hardware, Computer --- Computer systems --- Cybernetics --- Calculators --- Cyberspace --- Foundations